//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
//
//
//
// 示例 1：
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
//
//
// 示例 2：
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0]
//
//
//
// 限制：
//
//
// 0 <= k <= arr.length <= 10000
// 0 <= arr[i] <= 10000
//
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 561 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 最简单解法
function getLeastNumbers(arr: number[], k: number): number[] {


    return arr.sort((a,b) => a - b).slice(0,k)
};
//leetcode submit region end(Prohibit modification and deletion)

// ac地址：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
// 原文地址：https://xxoo521.com/2020-02-21-least-nums/

/**
 *
 * @param {number[]} arr
 * @param {number} start
 * @param {number} end
 * @return {number}
 */
function partition(arr, start, end) {
    const k = arr[start];
    let left = start + 1,
        right = end;
    while (1) {
        while (left <= end && arr[left] <= k) ++left;
        while (right >= start + 1 && arr[right] >= k) --right;

        if (left >= right) {
            break;
        }

        [arr[left], arr[right]] = [arr[right], arr[left]];
        ++left;
        --right;
    }
    [arr[right], arr[start]] = [arr[start], arr[right]];
    return right;
}

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
//? 剪枝的快速排序
/*
? 如果index = k，说明第 k 个元素已经放入正确位置，返回前 k 个元素
? 如果k < index，前 k 个元素在[left, index - 1]之间，缩小查找范围，继续查找
? 如果index < k，前 k 个元素在[index + 1, right] 之间，缩小查找范围，继续查找
 */
function getLeastNumbers2(arr: number[], k: number): number[]  {
    const length = arr.length;
    if (k >= length) return arr;
    let left = 0,
        right = length - 1;
    let index = partition(arr, left, right);
    while (index !== k) {
        if (index < k) {
            left = index + 1;
            index = partition(arr, left, right);
        } else if (index > k) {
            right = index - 1;
            index = partition(arr, left, right);
        }
    }

    return arr.slice(0, k);
};
